﻿//74. 搜索二维矩阵

//给你一个满足下述两条属性的 m x n 整数矩阵：
//每行中的整数从左到右按非严格递增顺序排列。
//每行的第一个整数大于前一行的最后一个整数。
//给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。


//两次查找
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target)
    {
        //二分查找
        int begin = 0, end = matrix.size() - 1, mid = (begin + end) / 2;
        while (begin <= end)
        {
            mid = (begin + end) / 2;
            if (matrix[mid][0] == target)
                return true;
            else if (matrix[mid][0] < target)
                begin = mid + 1;
            else
                end = mid - 1;
        }

        int x = begin - 1;
        if (x < 0)
            return false;
        end = matrix[0].size() - 1;
        begin = 0;
        while (begin <= end)
        {
            mid = (begin + end) / 2;
            if (matrix[x][mid] == target)
                return true;
            else if (matrix[x][mid] < target)
                begin = mid + 1;
            else
                end = mid - 1;
        }
        return false;
    }
};

//一次查找
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target)
    {
        //二分查找
        int m = matrix.size(), n = matrix[0].size();
        int begin = 0, end = m * n - 1, mid = (begin + end) / 2;
        while (begin <= end)
        {
            mid = (begin + end) / 2;
            if (matrix[mid / n][mid % n] == target)
                return true;
            else if (matrix[mid / n][mid % n] < target)
                begin = mid + 1;
            else
                end = mid - 1;
        }

        return false;
    }
};